package com.example.demo.arithmetic.datastructure.tree;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 * <p>
 * 一般来说，删除节点可分为两个步骤：
 * <p>
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 * }
 */
public class Leetcode430 {
    public TreeNode deleteNode(TreeNode root, int key) {
        // 删除二叉树节点
        // root 为空，代表未搜索到值为 key 的节点，返回空。
        if (root == null) {
            return null;
        }
        if (key < root.val) {
            // root.val>key，表示值为 key 的节点可能存在于 root 的左子树中，
            // 需要递归地在 root.left 调用 deleteNode，并返回 root。
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            // root.val<key，表示值为 key 的节点可能存在于 root 的右子树中，
            // 需要递归地在 root.right 调用 deleteNode，并返回 root。
            root.right = deleteNode(root.right, key);
        } else {
            // 找到了值为 key 的节点，需要删除它。
            if (root.left == null) {
                // root 左子树为空，直接返回 root 的右子树。
                return root.right;
            } else if (root.right == null) {
                // root 右子树为空，直接返回 root 的左子树。
                return root.left;
            } else {
                // root 左右子树均不为空，找到 root 在中序遍历下的前驱节点。
                TreeNode minNode = findMin(root.right);
                // 删除前驱节点。
                root.val = minNode.val;
                // 删除前驱节点。
                root.right = deleteNode(root.right, minNode.val);
            }
        }
        return root;
    }

    private TreeNode findMin(TreeNode right) {
        while (right.left != null) {
            right = right.left;
        }
        return right;
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n3 = new TreeNode(3);
        TreeNode n2 = new TreeNode(2, n1, n3);

        TreeNode n5 = new TreeNode(5);
        TreeNode n7 = new TreeNode(7);
        TreeNode n6 = new TreeNode(6, n5, n7);
        TreeNode root = new TreeNode(4, n2, n6);

        TreeNode treeNode = new Leetcode430().deleteNode(root, 3);

        System.out.println(treeNode);
    }
}
